package com.lw.leetcode.arr.b;

/**
 * 1010. 总持续时间可被 60 整除的歌曲
 *
 * @Author liw
 * @Date 2021/6/23 11:26
 * @Version 1.0
 */
public class NumPairsDivisibleBy60 {


    public static void main(String[] args) {
        NumPairsDivisibleBy60 test = new NumPairsDivisibleBy60();
        int[] arr = {60, 60, 60, 60};
//        int[] arr = {30, 20, 150, 100, 40};
        int i = test.numPairsDivisibleBy60(arr);
        System.out.println(i);
    }

    public int numPairsDivisibleBy60(int[] time) {
        int count = 0;
        int[] seconds = new int[60];
        for (int t : time) {
            seconds[t % 60] += 1;
        }
        count += combination(seconds[30], 2);
        count += combination(seconds[0], 2);
        int i = 1, j = 59;
        while (i < j) {
            count += seconds[i++] * seconds[j--];
        }
        return count;
    }

    // 求组合数
    public int combination(int n, int k) {
        long result = 1;
        for (int i = 1; i <= k; i++) {
            result = result * (n - i + 1) / i;
        }
        return (int) result;
    }

}
